package com.algorithm.ch1.lzr.string;

/**
 * 给定一个字符串, 验证它是否是回文串, 只考虑字母和数字字符, 可以忽略字母的大小写
 * <p>
 * 输入: "A man, a plan, a canal: Panama"
 * 输出: true
 * <p>
 * 输入: "race a car"
 * 输出: false
 *
 * @author lzr
 * @date 2018/8/13
 */
public class IsPalindrome {

    public static void main(String[] args) {

        String s1 = "A man, a plan, a canal: Panama";
        boolean palindrome1 = isPalindrome1(s1);
        System.out.println(palindrome1);

        String s2 = "A man, a plan, a canal: Panama";
        boolean palindrome2 = isPalindrome2(s2);
        System.out.println(palindrome2);

    }

    /**
     * 使用正则匹配出字母跟数字(运行效率比较慢, 不使用api去筛选转换字母数字, 使用方式2实现)
     *
     * @param s
     * @return
     */
    public static boolean isPalindrome1(String s) {
        //先筛选出大写字母,小写字母,数字
        s = s.replaceAll("[^A-Za-z0-9]+", "").toLowerCase();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != chars[chars.length - 1 - i]) {
                return false;
            }
        }
        return true;
    }


    /**
     * 基于方法1进行优化
     *
     * @param s
     * @return
     */
    public static boolean isPalindrome2(String s) {
        if (s.length() == 0 || s.length() == 1) {
            return true;
        }
        char[] chars = s.toCharArray();
        int start = 0;
        int end = chars.length - 1;
        while (start < end) {
            if (!isRequiredChar(chars[start])) {
                start++;
            } else if (!isRequiredChar(chars[end])) {
                end--;
            } else if (!compareChar(chars[start], chars[end])) {
                break;
            } else {
                start++;
                end--;
            }
        }
        return start >= end;
    }

    /**
     * 判断是否是指定字符
     *
     * @param c
     * @return
     */
    private static boolean isRequiredChar(char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
    }

    /**
     * 字符符合条件的情况下, 判断是否相等
     *
     * @param startChar
     * @param endChar
     * @return
     */
    private static boolean compareChar(char startChar, char endChar) {
        if (startChar >= 'A' && startChar <= 'Z') {
            startChar = Character.toLowerCase(startChar);
            //int i = startChar + 32;
            //startChar = (char)i;
        }
        if (endChar >= 'A' && endChar <= 'Z') {
            endChar = Character.toLowerCase(endChar);
            //int i = endChar + 32;
            //endChar = (char)i;
        }
        if (startChar == endChar) {
            return true;
        } else {
            return false;
        }
    }
}
